#include<iostream>
#include<vector>
#include<stack>
#include<string>
#include<queue>
#include<algorithm>
#include<unordered_set>
using namespace std;



class Solution{//有向无环图
    private:
    vector<vector<int>>edges;
    vector<int> visited;
    vector<int> ret;
    bool valid = true;

    public:
    //dfs
    void dfs(int u){
        visited[u] = 1;
        for(int v: edges[u]){
            if(visited[v] == 0){
                dfs(v);
                if(!valid){
                    return;
                }
            }else if(visited[v] == 1){
                valid = false;
                return;
            }
        }
        visited[u] = 2;
        ret.push_back(u);
    }

    vector<int> ans1(int numCourses, vector<vector<int>>& prerequisites){
        edges.clear();
        visited.clear();
        ret.clear();
        edges.resize(numCourses);
        visited.resize(numCourses);
        for(auto& info: prerequisites){
            edges[info[1]].push_back(info[0]);
        }
        for(int i = 0; i != numCourses; i++){
            if(!visited[i]){
                dfs(i);
            }
        }
        if(!valid){
            return {};
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }

    //bfs
    vector<int> ans2(int numCourses, vector<vector<int>>& prerequisites){
        edges.clear();
        ret.clear();
        visited.clear();
        edges.resize(numCourses);
        visited.resize(numCourses);
        for(auto& info: prerequisites){
            edges[info[1]].push_back(info[0]);
            visited[info[0]]++;
        }

        queue<int> q;
        for(int i = 0; i != numCourses; i++){
            if(visited[i] == 0){
                q.push(i);
            }
        }

        int temp = 0;
        while(!q.empty()){
            temp++;
            int u = q.front();
            q.pop();
            for(int v: edges[u]){
                visited[v]--;
                if(visited[v] == 0){
                    q.push(v);
                }
            }
            ret.push_back(u);
        }

        if(ret.size() != numCourses){
            return {};
        }
        return ret;
    }

    
};

void show(vector<auto>& num){
    int len = num.size();
    for(int i = 0; i != len-1; i++){
        cout << num[i] << " " << ends;
    }
    cout << num[len-1] << endl;
}

void test1(){
    vector<vector<int>> pre = {
        {1,0}
    };
    int numCourse = 2;

    Solution s;
    vector<int> ret = s.ans1(numCourse, pre);
    // vector<int> ret = s.ans2(numCourse, pre);
    show(ret);
    
}

void test2(){
    vector<vector<int>> pre = {
        {1,0},
        {2,0},
        {3,2},
        {3,1}
    };
    int numCourse = 4;

    Solution s;
    // vector<int> ret = s.ans1(numCourse, pre);
    vector<int> ret = s.ans2(numCourse, pre);
    show(ret);
    
}



int main(void){
    test1();
    cout << "-----------------------------" << endl;
    test2();

    return 0;
}